package DP.子序列;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    就2种情况p[cI],p[cI]+son（没有什么3种情况
    只是return不能用maxRes这个全局值【因为子串是连续的,不能跳着拿max】，用局部curMax即可
 */
public class 子串________最大子串和53 {
    /*back*/
    int[] p; int n;
    int maxSum = Integer.MIN_VALUE;
    public int maxSubArray(int[] nums) {
        p=nums;n=nums.length;
        //必须全全遍历，可能第一个是负数

        for (int i = 0; i < n; i++) {
            int cI = i;
            back(cI);
        }
        return maxSum;
    }
    Map<String, Integer> map = new HashMap<>();
    private int back(int cI) {
        if(cI==n){
            return 0;
        }

        int L = back(cI + 1);

        int curM = Math.max(L+p[cI], p[cI]);

        //res统计max
        maxSum = Math.max(curM,maxSum);
        //return是可达路径cur
        return curM;
    }

    /*
        [dp]
        要么自成一派，要么跟随前面
    */
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int[] dp = new int[nums.length]; int n = nums.length;
        dp[0] = nums[0];
        int max = nums[0];
        //到n
        for (int i = 1; i < n ; i++) {
            dp[i] = Math.max(dp[i-1],nums[i]+dp[i-1]);
            max =Math.max(dp[i],max);
        }
        System.out.println(max);
    }
}
